跳到主要内容

高级排序算法 希尔排序

高级排序是什么？​

之前学习的简单排序的时间复杂度都是 O(N2)O(N^2) ,而平方阶会随着输入的规模增大，时间成本急剧上升，所以这些排序方法不能用于更大规模的问题

希尔排序的时间复杂度​

希尔排序（Shell Sort）的最好的复杂度大概能到 O(n1.2)O(n^{1.2}) 到 O(n1.3)O(n^{1.3}) 的样子，主要受选择的增量序列影响，但是最好也达不到 O(nlogn)O(nlogn) ,因此它一般情况是干不过快排的

快排理论上要比希尔排序快，如果自己实现的快排比希尔慢的原因，主要估计还是因为用了函数递归的缘故（快排是标准的递归算法，一般用递归函数实现）。如果没对递归做优化，那么递归本身的时间开销可能会超过排序的开销。

希尔排序是什么？​

希尔排序是插入排序的一种改进版本，下先来看下插入排序的缺点

插入排序的缺点：

  1. 在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
  2. 但插入排序一般来说是低效的，因为插入排序 每次只能将数据移动一位；

所以希尔排序就是结合上面特点，创造出插入排序最适合的环境

  1. 基本有序
  2. 待排序的数据量小

改进思路：

先将整个待排元素序列分割成若干个子序列（由相隔某个 “增量” 的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。

如何让待排序的数据量小，且基本有序呢？就将原本大量的数据进行分组，然后将它们各自排序，再合并？

{9，1，5，8，3，7，4，6，2}
拆成三组
{9，1，5} {8，3，7} {4，6，2}
各种排序再拼在一起
{1，5，9，3，7，8，2，4，6}

如上所示，这样得到的数据并不算基本有序

基本有序是像下面这样：小的关键字基本在前面，大的基本在后面，不大不小的在中间

{2，1，3，6，4，7，5，8，9}

所以希尔排序就是要解决这块问题。

上面分割待排序序列目的是减少待排序序列的个数，并使整个序列向基本有序发展。而上面这样分完组后就各自排序的方法是达不到这样的要求的。因此需要采用 跳跃分割的策略：将相距某个 “增量” （分组长度）的记录组成一个子序列，这样才能保证在子序列内进行直接插入排序后得到的结果是基本有序而不是局部有序的（希尔算法的性能与所选取的增量序列有很大关系）

希尔排序的步骤

  1. 选定一个增长量 h，按照增长量 h 作为数据分组的依据，对数据进行分组
  2. 对分好组的每一组数据完成插入排序
  3. 减小增长量（最小减为 1），不断重复第二步操作

如下图，不断的减小增量（这里选择 h = h / 2 的方式）

如下可见，本质就是把它们打散，使之更均匀的分，例如这里的 8 和 3 把小的这个 3 丢到前面来，大的这个 8 丢到了后面去了，再下一组 9 和 5，把小的 5 丢前面，大的 9 丢后面

所以说，希尔排序之所以那么快，是因为一次可以排多个，使之基本有序

这里增量 h 的确定方式：增长量 h的值每一固定的规则（注意，这里只是最常用的增量算法，还有其它的增量算法）

int h = 1
while (h < arr.length / 2) {
    h = 2h + 1;
}

// 循环结束后就可以确定 h的最大值了
// h 的减小规则为： h = h/2

注意：在希尔排序中，增长量 h 并没有固定的规则，也没有最好一说

交换式希尔排序​

在前面的插入排序也可以用这种方式，有点像冒泡的方式更新位置，虽然直观，不过它并不是最优的方法，一般还是下面那种移位式排序

public class Shell {
    public static <T extends Comparable<T>> void sort(T[] a) {
        // 先确定 h值
        int h = 1;
        while (h < a.length / 2) {
            h = 2 * h + 1;
        }

        // 希尔排序
        while (h >= 1) {
            // 找到待插入的元素
            for (int i = h; i < a.length; i++) {
                // 把待插入的元素插入到有序数列中
                for (int j = i; j >= h; j -= h) {
                    // 待插入的元素是 a[j], 比较 a[j] 和 a[j-h]
                    if (greater(a[j - h], a[j])) {
                        exchange(a, j, j - h);
                    } else {
                        break;
                    }
                }
            }
            // 减小 h的值
            h = h / 2;
        }
    }

    private static <T extends Comparable<T>> boolean greater(T v, T w) {
        return v.compareTo(w) > 0;
    }

    private static <T extends Comparable<T>> void exchange(T[] a, int i, int j) {
        T temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

移位式希尔排序​

如下算法比较一下之前所学的插入排序，可以发现它实际就增加了一个 h

public class Shell {
    public static <T extends Comparable<T>> void sort(T[] arr) {
        int length = arr.length;
        T temp;

        // 先确定 h值
        int h = 1;
        while (h < length / 2) {
            h = 2 * h + 1;
        }

        // 希尔排序
        while (h >= 1) {
            // 这里从 h 开始是因为像插入排序那样，从第一个开始插入，又因为分成了 h 组，
            // 所以有 h 个待插的，即从 h 开始迭代（看上图，8 9 1 7 2 就是头）
            // 而这里的 i 的最大取值是数组的总长度，是因为每组的最后一个数的索引 = 数组总长度 - 步长
            for (int i = h; i < length; i++) {
                temp = arr[i];
                // 从已经排序的序列最右边的开始比较，找到比其小的数
                int j = i - h;

                // 如果比 a[i] 大的需要把值往后移动 h 位，即 a[j - h] 挪到 a[j]
                while (j >= 0 && greater(arr[j], temp)) {
                    arr[j + h] = arr[j];
                    j -= h;
                }

                arr[j + h] = temp;
            }

            // 减小 h的值
            h = h / 2;
        }
    }

    private static <T extends Comparable<T>> boolean greater(T v, T w) {
        return v.compareTo(w) > 0;
    }
}

计算希尔排序的时间复杂度​

由于希尔排序的时间复杂度分析过于复杂（很多数学知识），对于这种分析起来比较复杂的算法可以采用事后分析法

直接分析最坏的情况，全部逆序的情况

public class Temp {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        for (int i = 100000; i >0 ; i--) {
            list.add(i);
        }

        Integer[] a = new Integer[list.size()];
        list.toArray(a);
        testShell(a);
    }

    // 30 毫秒
    public static void testShell(Integer[] a) {
        long start = System.currentTimeMillis();
        Shell.sort(a);
        long end = System.currentTimeMillis();
        System.out.println("希尔排序执行时间为：" + (end - start) + "毫秒");
    }

    // 31972毫秒
    public static void testBubble(Integer[] a) {
        long start = System.currentTimeMillis();
        Bubble.sort(a);
        long end = System.currentTimeMillis();
        System.out.println("冒泡排序执行时间为：" + (end - start) + "毫秒");
    }
}
  1. 最好情况：序列是正序排列，在这种情况下，需要进行的比较操作需（n-1）次。后移赋值操作为0次。即 O(n)O(n)
  2. 最坏情况: O(nlog2n)O(nlog2n) 。
  3. 渐进时间复杂度（平均时间复杂度）: O(nlog2n)O(nlog2n)